package com.zxy.leetcode._00000_00099._00060_00069;

/**
 * https://leetcode-cn.com/problems/unique-paths-ii/
 *
 * 不同路径 II
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 *
 * com.zxy.leetcode._00000_00099._00060_00069.Test00062 的改版
 *
 * 标签：动态规划
 */
public class Test00063 {

    public static void main(String[] args) {
        Test00063 test = new Test00063();
        int[][] obstacleGrid = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };
        System.out.println(test.uniquePathsWithObstacles(obstacleGrid));
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        int[][] dp = obstacleGrid;

        int m = dp.length;
        int n = dp[0].length;

        // 在原数组上处理，是为了省空间
        // 初始化，两边置为1，障碍物不可过的，变负数
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (dp[i][j] == 1) {
                    dp[i][j] = -dp[i][j];
                }else if (i==0 && j==0) {
                    dp[i][j] = 1;
                }else if (i==0 && j>0) {
                    if (dp[i][j-1] < 0) {
                        dp[i][j] = -1;
                    }else {
                        dp[i][j] = 1;
                    }
                }else if (i>0 && j==0) {
                    if (dp[i-1][j] < 0) {
                        dp[i][j] = -1;
                    }else {
                        dp[i][j] = 1;
                    }
                }
            }
        }

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (i==0 || j==0) {
                    continue;
                }
                // 当前节点不可过
                if (dp[i][j] < 0) {
                    continue;
                }
                if (dp[i-1][j] > 0) {
                    dp[i][j] += dp[i-1][j];
                }
                if (dp[i][j-1] > 0) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        if (dp[m-1][n-1] <= 0) {
            return 0;
        }
        return dp[m-1][n-1];
    }
}
